package Test.offer;

import java.util.ArrayDeque;

/**
 * @ClassName P59
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/8/3 11:50
 * @Version 1.0
 */
public class P59 {
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    int[] nums;

    public int[] maxSlidingWindow(int[] nums, int k) {
        this.nums = nums;

        int n = nums.length;
        if (n * k == 0) return nums;
        if (k == 1) return nums;

        //初始化
        int maxIdx = 0;
        for (int i = 0; i < k; i++) {
            cleanDq(i, k);
            queue.addLast(i);
            if (nums[i] > nums[maxIdx]) maxIdx = i;
        }
        int[] output = new int[n - k + 1];
        output[0] = nums[maxIdx];

        for (int i = k; i < n; i++) {
            cleanDq(i, k);
            queue.addLast(i);
            output[i - k + 1] = nums[queue.getFirst()];
        }
        return output;
    }

    private void cleanDq(int idx, int k) {
        //首先清除超出窗口的
        while (!queue.isEmpty() && queue.getFirst() <= idx - k) {
            queue.removeFirst();
        }

        //然后清理比num[idx]小的
        while (!queue.isEmpty() && nums[queue.getLast()] < nums[idx]) {
            queue.removeLast();
        }
    }
}
